package com.sheng.leetcode.year2022.month05.day13;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/05/13
 *
 * 面试题 01.05. 一次编辑
 * 字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。
 * 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
 *
 * 示例 1:
 *
 * 输入:
 * first = "pale"
 * second = "ple"
 * 输出: True
 *
 * 示例 2:
 *
 * 输入:
 * first = "pales"
 * second = "pal"
 * 输出: False
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/one-away-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class LeetCodeOneEditAway {

    @Test
    public void test01(){
//        String first = "pale";
//        String second = "ple";
        String first = "pales";
        String second = "pal";
        System.out.println(new Solution().oneEditAway(first, second));
    }

}
class Solution {
    public boolean oneEditAway(String first, String second) {
        //如果两个字符串长度差距大于1，则一次修改内绝对无法匹配，直接返回false
        if (Math.abs(first.length() - second.length()) > 1) {
            return false;
        }
        String str1, str2;
        if (first.length() >= second.length()) {
            str1 = second;
            str2 = first;
        } else {
            str2 = second;
            str1 = first;
        }
        int n = str1.length();
        int m = str2.length();
        int i = 0, j = 0, count = 0;
        while (i < n && j< m) {
            //相同位置上的字符相等，则比较下一个位置上的字符
            if (str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            } else {
                //两种情况，如果两个字符串长度相等，那么直接进行修改即可，总修改次数加一
                //如果两个字符串长度不相等，那么则可以在长度小的那一边塞入一个字符，然后继续拿当前字符和另一条字符串的后一个字符比较
                if (n == m) {
                    i++;
                    j++;
                    count++;
                } else {
                    j++;
                    count++;
                }
            }
        }
        //滑块问题
        return count <= 1;
    }
}
